#include "types.h"
#include "defs.h"
#include "param.h"
#include "memlayout.h"
#include "mmu.h"
#include "x86.h"
#include "proc.h"
#include "spinlock.h"

struct {
  struct spinlock lock;
  struct proc proc[NPROC];
} ptable;                             // 全局进程管理数据结构

static struct proc *initproc;         // init 进程的指针

int nextpid = 1;
extern void forkret(void);
extern void trapret(void);

static void wakeup1(void *chan);

void
pinit(void)
{
  initlock(&ptable.lock, "ptable");
}

//PAGEBREAK: 32
// Look in the process table for an UNUSED proc.
// If found, change state to EMBRYO and initialize
// state required to run in the kernel.
// Otherwise return 0.
// Must hold ptable.lock.
static struct proc*
allocproc(void)
{
  struct proc *p;           // 用于指向新分配的PCB
  char *sp;

  // 遍历进程的PCB数组
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
    if(p->state == UNUSED)  // 找到一个空闲PCB
      goto found;
  return 0;

found:
  p->state = EMBRYO;          // 初始化为“胚胎态”
  p->pid = nextpid++;
  p->slot = SLOT;             // 初始化进程是分配时间片
  p->priority = DEFAULT_PRI;  // default priority
  p->shm = KERNBASE;          // 初始化shm，刚开始shm与KERNBASE重合
  p->shmkeymask = 0;          // 初始化shmkeymask
  p->mqmask = 0;              // 初始化 mqmask
  for (int i = 0; i < 10; i++)
  {
    p->vm[i].next = -1;
    p->vm[i].length = 0;
  }
  p->vm[0].next = 0;

  // Allocate kernel stack. // 分配内核栈
  if((p->kstack = kalloc()) == 0){    // kalloc()分配KSTACKSIZE=4096字节
    p->state = UNUSED;                // 进程状态仍为“未使用”
    return 0;
  }
  sp = p->kstack + KSTACKSIZE;        // 堆栈指针指向栈底

  // Leave room for trap frame.
  sp -= sizeof *p->tf;                // 留下 trap frame空间
  p->tf = (struct trapframe*)sp;      // tf指向上面的空间

  // Set up new context to start executing at forkret,
  // which returns to trapret.
  sp -= 4;                            // 堆栈中占用4字节
  *(uint*)sp = (uint)trapret;         // 用于保存 trapret（代码起始位置）

  sp -= sizeof *p->context;           // 堆栈中占用 context 大小的空间
  p->context = (struct context*)sp;   // 用于本进程的 context
  memset(p->context, 0, sizeof *p->context);
  p->context->eip = (uint)forkret;    // 本进程的 context 中只有eip指向forkret

  return p;
}

//PAGEBREAK: 32
// Set up first user process.         // 创建第一个用户态进程
void
userinit(void)
{
  struct proc *p;
  extern char _binary_initcode_start[], _binary_initcode_size[];

  acquire(&ptable.lock);              // 获得 ptable 锁

  p = allocproc();                    // 分配 PCB，proc
  initproc = p;                       // 用于引用 init 进程的全局变量
  if((p->pgdir = setupkvm()) == 0)    // 创建内核的创始页表
    panic("userinit: out of memory?");
  inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size);
  p->sz = PGSIZE;
  memset(p->tf, 0, sizeof(*p->tf));         // 下面构造 trapframe
  p->tf->cs = (SEG_UCODE << 3) | DPL_USER;  // 用户代码段
  p->tf->ds = (SEG_UDATA << 3) | DPL_USER;  // 用户数据段
  p->tf->es = p->tf->ds;                    // es段和数据段重合
  p->tf->ss = p->tf->ds;                    // ss段和数据段重合
  p->tf->eflags = FL_IF;
  p->tf->esp = PGSIZE;
  p->tf->eip = 0;  // beginning of initcode.S

  safestrcpy(p->name, "initcode", sizeof(p->name));   // 设置进程名为 initcode
  p->cwd = namei("/");                                // 设置工作目录为"/"

  p->state = RUNNABLE;        // 状态改为 RUNNABLE

  release(&ptable.lock);      // 释放 ptable 锁
}

// Grow current process's memory by n bytes.    // 扩大/缩小进程的内存空间
// Return 0 on success, -1 on failure.
int
growproc(int n)       // 被 sbrk 系统调用所使用
{
  uint sz;

  sz = proc->sz;
  if(n > 0){          // 扩大、分配内存
    if((sz = allocuvm(proc->pgdir, sz, sz + n)) == 0)
      return -1;
  } else if(n < 0){   // 缩小、回收内存
    if((sz = deallocuvm(proc->pgdir, sz, sz + n)) == 0)
      return -1;
  }
  proc->sz = sz;
  switchuvm(proc);    // 启用新页表（同时会刷新TLB）
  return 0;
}

// Create a new process copying p as the parent.      // 创建进程的 fork 操作
// Sets up stack to return as if from system call.
// Caller must set state of returned proc to RUNNABLE.
int
fork(void)
{
  int i, pid;
  struct proc *np;

  acquire(&ptable.lock);

  // Allocate process.
  if((np = allocproc()) == 0){      // 分配进程控制块
    release(&ptable.lock);
    return -1;
  }

  // Copy process state from p.
  if((np->pgdir = copyuvm(proc->pgdir, proc->sz)) == 0){  // 复制进程映像
    kfree(np->kstack);          // if fail，释放内核栈
    np->kstack = 0;             // if fail，将 kstack 清零
    np->state = UNUSED;         // if fail，将 state 设置为 UNUSED
    release(&ptable.lock);      // if fail，释放 ptable 锁
    return -1;
  }

  /* lab2：共享内存实验 begin */
  shmaddcount(proc->shmkeymask);        // fork出新进程，所以引用计数加一
  np->shm = proc->shm;                  // 复制父进程的shm
  np->shmkeymask = proc->shmkeymask;    // 复制父进程的shmkeymask
  for ( i = 0; i < 8; i++)              // 复制父进程的shmva数组
  {
    if (shmkeyused(i, np->shmkeymask))  // 只复制已启用的共享内存区
    {
      np->shmva[i] = proc->shmva[i];
    }
  }
  /* lab2：共享内存实验 end */

  /* lab2：共享内存实验 begin */
  addmqcount(proc->mqmask);     // 父进程持有的消息队列的引用数全部加一
  np->mqmask = proc->mqmask;    // 复制父进程的mqmask
  /* lab2：共享内存实验 end */

  np->sz = proc->sz;      // 子进程和父进程大小一样
  np->parent = proc;      // 子进程的parent指向父进程
  *np->tf = *proc->tf;    // 子进程的tf和父进程的tf相同，都返回到用户态调用fork后一条指令

  // Clear %eax so that fork returns 0 in the child.
  np->tf->eax = 0;        // 父子进程tf的唯一区别：子进程返回值为0

  for(i = 0; i < NOFILE; i++)   // 复制已打开的文件描述符
    if(proc->ofile[i])
      np->ofile[i] = filedup(proc->ofile[i]);
  np->cwd = idup(proc->cwd);

  safestrcpy(np->name, proc->name, sizeof(proc->name));   // 父子进程同名

  pid = np->pid;            // 新创建的子进程PID

  np->state = RUNNABLE;     // 子进程设置为可运行RUNNABLE

  release(&ptable.lock);

  return pid;               // 父进程返回子进程 PID
}

// Exit the current process.  Does not return.    // 进程退出的exit操作
// An exited process remains in the zombie state
// until its parent calls wait() to find out it exited.
void
exit(void)
{
  struct proc *p;
  int fd;

  if(proc == initproc)          // init进程不允许 exit 结束
    panic("init exiting");

  // Close all open files.
  for(fd = 0; fd < NOFILE; fd++){ // 关闭所有已打开的文件
    if(proc->ofile[fd]){
      fileclose(proc->ofile[fd]);
      proc->ofile[fd] = 0;
    }
  }

  begin_op();         // 每次FS调用前执行
  iput(proc->cwd);
  end_op();           // 每次FS调用后执行
  proc->cwd = 0;      // 工作目录为空

  acquire(&ptable.lock);

  // Parent might be sleeping in wait().
  wakeup1(proc->parent);    // 唤醒父进程（如果父进程wait睡眠的话）

  // Pass abandoned children to init.   // 如果有子进程，交给init接收孤儿进程
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){   // 遍历所有进程
    if(p->parent == proc){      // 找到自己的一个子进程
      p->parent = initproc;     // 该进程由 init 进程收养
      if(p->state == ZOMBIE)    // 如果该子进程已经处于ZOMBIE状态
        wakeup1(initproc);      // 则由 init 进程完成清理工作
    }
  }

  // Jump into the scheduler, never to return.
  proc->state = ZOMBIE;         // 进程状态设置为 ZOMBIE状态
  sched();                      // 调度切换到其他进程
  panic("zombie exit");         // 正常不会执行到这里，否则panic
}

// Wait for a child process to exit and return its pid.   // 等待子进程结束
// Return -1 if this process has no children.
int
wait(void)
{
  struct proc *p;
  int havekids, pid;

  acquire(&ptable.lock);
  for(;;){
    // Scan through table looking for zombie children.
    havekids = 0;
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){   // 扫描所有的进程
      if(p->parent != proc)     // 不是自己的进程则直接跳过
        continue;
      havekids = 1;             // 发现一个子进程
      if(p->state == ZOMBIE){   // 处于 ZOMBIE 状态
        // Found one.
        pid = p->pid;
        kfree(p->kstack);       // 释放内核栈空间
        p->kstack = 0;          // 对内核栈指针清零

        /* lab2：共享内存实验 begin */
        shmrelease(p->pgdir, p->shm, p->shmkeymask);  // 解除共享内存映射
        p->shm = KERNBASE;                            // 重置shm
        p->shmkeymask = 0;                            // 把shmkeymask重置
        /* lab2：共享内存实验 end */

        /* lab2：消息队列实验 begin */
        releasemq2(p->mqmask);  // 回收消息队列
        p->mqmask = 0;          // 重置进程的mqmask
        /* lab2：消息队列实验 end */

        freevm(p->pgdir);       // 接触页表映射、释放用户空间占用的页帧
        p->pid = 0;             // 对 pid 清零
        p->parent = 0;          // 对 parent 清零
        p->name[0] = 0;         // 进程名清零
        p->killed = 0;
        p->state = UNUSED;      // 状态修改为 UNUSED
        release(&ptable.lock);  // 释放 ptable 锁
        return pid;
      }
    }

    // No point waiting if we don't have any children.
    if(!havekids || proc->killed){    // 没有子进程或者已经退出的进程
      release(&ptable.lock);
      return -1;
    }

    // Wait for children to exit.  (See wakeup1 call in proc_exit.)
    sleep(proc, &ptable.lock);  //DOC: wait-sleep   // 睡眠等待子进程退出
  }
}

//PAGEBREAK: 42
// Per-CPU process scheduler.   // 调度函数，每个CPU上各自执行一份
// Each CPU calls scheduler() after setting itself up.
// Scheduler never returns.  It loops, doing:
//  - choose a process to run
//  - swtch to start running that process
//  - eventually that process transfers control
//      via swtch back to the scheduler.
void
scheduler(void)
{
  struct proc *p, *temp;
  int priority;
  int needed = 1;     //是否需要重新搜索最高优先级

  for(;;){      // scheduler 函数不返回，无限循环
    // Enable interrupts on this processor.
    sti();      // 需要开中断

    // Loop over process table looking for process to run.
    acquire(&ptable.lock);
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      if (needed)
      {
        priority = 19;
        // 获取可运行的最高优先级
        for(temp = ptable.proc; temp < &ptable.proc[NPROC]; temp++)
        {
          if (temp->state == RUNNABLE && temp->priority < priority)
          {
            priority = temp->priority;
          }
        }
      }
      needed = 0;

      if(p->state != RUNNABLE)    // 不关注非 RUNNABLE 的进程（只关注就绪进程）
        continue;
      if (p->priority > priority)
        continue;

      // Switch to chosen process.  It is the process's job
      // to release ptable.lock and then reacquire it
      // before jumping back to us.
      proc = p;                   // 找到一个就绪进程
      if (p->name[0] == 'p')
      {
        cprintf("......PID=%d prio=%d %s\n", p->pid, p->priority, p->name);
      }
      
      switchuvm(p);               // 完成进程的用户空间切换，此时仍在 scheduler() 内核空间中
      p->state = RUNNING;         // 将进程状态修改为 RUNNING
      swtch(&cpu->scheduler, p->context); // 完成运行环境的切换（context切换）
      switchkvm();                // 从进程页表切换到 scheduler() 页表

      // Process is done running for now.   // 开始下一次调度，选择新的就绪进程
      // It should have changed its p->state before coming back.
      proc = 0;
      needed = 1;
    }
    release(&ptable.lock);

  }
}

// Enter scheduler.  Must hold only ptable.lock       // 必须持有ptable.lock
// and have changed proc->state. Saves and restores
// intena because intena is a property of this
// kernel thread, not this CPU. It should
// be proc->intena and proc->ncli, but that would
// break in the few places where a lock is held but
// there's no process.
void
sched(void)
{
  int intena;

  if(!holding(&ptable.lock))
    panic("sched ptable.lock");
  if(cpu->ncli != 1)
    panic("sched locks");
  if(proc->state == RUNNING)        // 进程不能处于 RUNNING 状态
    panic("sched running");
  if(readeflags()&FL_IF)
    panic("sched interruptible");
  intena = cpu->intena;
  swtch(&proc->context, cpu->scheduler);  // 切换现场
  cpu->intena = intena;             // 此时 intena 是切入进程的堆栈变量
}

// Give up the CPU for one scheduling round.  // 让出 CPU
void
yield(void)
{
  acquire(&ptable.lock);  //DOC: yieldlock
  proc->state = RUNNABLE;   // 状态修改为 RUNNABLE
  sched();                  // 调度切换
  release(&ptable.lock);
}

// A fork child's very first scheduling by scheduler()  // 子进程的执行起点
// will swtch here.  "Return" to user space.
void
forkret(void)
{
  static int first = 1;
  // Still holding ptable.lock from scheduler.
  release(&ptable.lock);

  if (first) {
    // Some initialization functions must be run in the context
    // of a regular process (e.g., they call sleep), and thus cannot
    // be run from main().
    first = 0;
    iinit(ROOTDEV);
    initlog(ROOTDEV);
  }

  // Return to "caller", actually trapret (see allocproc).
}

// Atomically release lock and sleep on chan.   // 睡眠、阻塞
// Reacquires lock when awakened.
void
sleep(void *chan, struct spinlock *lk)    // chan 标识某个阻塞队列
{
  if(proc == 0)                 // 本地进程指针为 NULL（不可能发生事件）
    panic("sleep");

  if(lk == 0)                   // 必须传入一个自旋锁
    panic("sleep without lk");

  // Must acquire ptable.lock in order to
  // change p->state and then call sched.
  // Once we hold ptable.lock, we can be
  // guaranteed that we won't miss any wakeup
  // (wakeup runs with ptable.lock locked),
  // so it's okay to release lk.
  if(lk != &ptable.lock){  //DOC: sleeplock0
    acquire(&ptable.lock);  //DOC: sleeplock1   // 需持有 ptable.lock 的保护
    release(lk);            // 释放 lk
  }

  // Go to sleep.
  proc->chan = chan;        // 挂到睡眠阻塞链上
  proc->state = SLEEPING;   // 状态修改为 SLEEPING
  sched();                  // 调度切换

  // Tidy up.         // 被再次唤醒后从这里开始执行
  proc->chan = 0;     // 不再处于睡眠阻塞链上
  // 此时从 wakeip() 过来，应该持有 ptable.lock
  // Reacquire original lock.
  if(lk != &ptable.lock){  //DOC: sleeplock2
    release(&ptable.lock);  // 解除 ptable.lock 保护
    acquire(lk);
  }
}

//PAGEBREAK!
// Wake up all processes sleeping on chan.  // 唤醒阻塞链上的所有进程
// The ptable lock must be held.            // 此时已持有 ptable.lock
static void
wakeup1(void *chan)
{
  struct proc *p;

  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)  // 遍历所有进程
    if(p->state == SLEEPING && p->chan == chan)       // 只唤醒等待 chan 事件的进程
      p->state = RUNNABLE;
}

// Wake up all processes sleeping on chan.  // 唤醒阻塞链上的所有进程
void
wakeup(void *chan)    // 需要传入 chan 指名唤醒那个事件上的进程
{
  acquire(&ptable.lock);
  wakeup1(chan);      // 由 wakeup1() 来执行具体的唤醒操作
  release(&ptable.lock);
}

// 仅唤醒等待指定信号量的一个进程
void wakeup1p(void * chan)
{
  acquire(&ptable.lock);
  struct proc *p;
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
  {
    if (p->state == SLEEPING && p->chan == chan)
    {
      p->state = RUNNABLE;
      break;
    }
  }
  release(&ptable.lock);
}

// Kill the process with the given pid.   // 撤销某个进程
// Process won't exit until it returns
// to user space (see trap in trap.c).
int
kill(int pid)
{
  struct proc *p;

  acquire(&ptable.lock);
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
    if(p->pid == pid){          // 找到指定进程的 pid
      p->killed = 1;            // 设置撤销标志
      // Wake process from sleep if necessary.
      if(p->state == SLEEPING)  // 如果处于 SLEEPING 状态
        p->state = RUNNABLE;    // 则将状态设置为 RUNNABLE
      release(&ptable.lock);
      return 0;                 // 完成撤销标志的设置
    }
  }
  release(&ptable.lock);
  return -1;
}

//PAGEBREAK: 36
// Print a process listing to console.  For debugging.    // 打印进程列表到控制台
// Runs when user types ^P on console.
// No lock to avoid wedging a stuck machine further.
void
procdump(void)
{
  static char *states[] = {
  [UNUSED]    "unused",
  [EMBRYO]    "embryo",
  [SLEEPING]  "sleep ",
  [RUNNABLE]  "runble",
  [RUNNING]   "run   ",
  [ZOMBIE]    "zombie"
  };
  int i;
  struct proc *p;
  char *state;
  uint pc[10];

  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){   // 遍历所有的进程
    if(p->state == UNUSED)    // 跳过未使用的 PCB
      continue;
    if(p->state >= 0 && p->state < NELEM(states) && states[p->state])
      state = states[p->state]; // 获取进程状态的字符串
    else
      state = "???";            // 无法识别的状态表示为 ？？？（不可能事件）
    cprintf("slice left:%d ticks.\n", p->slot);
    cprintf("PID=%d state=%s prio=%d %s:", p->pid, state, p->priority, p->name);
    cprintf("%d %s %s", p->pid, state, p->name);  // 打印进程号、状态、程序名

    /* lab2：内存管理实验 begin */
    for (int i = p->vm[0].next; i != 0; i = p->vm[i].next)
    {
      cprintf("start:%d, length:%d\n", p->vm[i].address, p->vm[i].length);
    }
    /* lab2：内存管理实验 end */
    
    if(p->state == SLEEPING){
      getcallerpcs((uint*)p->context->ebp+2, pc);
      for(i=0; i<10 && pc[i] != 0; i++)
        cprintf(" %p", pc[i]);
    }
    cprintf("\n");
    cprintf("\n");
  }
}

// chpri() 函数的实现
int
chpri(int pid, int priority)
{
  struct proc * p;
  acquire(&ptable.lock);
  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
  {
    if (p->pid == pid)
    {
      p->priority = priority;
      break;
    }
  }
  release(&ptable.lock);
  return pid;
}

int 
mygrowproc(int n){                 // 实现首次最佳适应算法
	struct vma *vm = proc->vm;     // 遍历寻找合适的空间
	int start = proc->sz;          // 寻找合适的分配起点
	int index;
	int prev = 0;
	int i;

	for(index = vm[0].next; index != 0; index = vm[index].next){
		if(start + n < vm[index].address)
			break;
		start = vm[index].address + vm[index].length;
		prev = index;
	}
	
	for(i = 1; i < 10; i++) {            // 寻找一块没有用的 vma 记录新的内存块
		if(vm[i].next == -1){
			vm[i].next = index;			
			vm[i].address = start;
			vm[i].length = n;

			vm[prev].next = i;
			
			myallocuvm(proc->pgdir, start, start + n);
			switchuvm(proc);
			return start;   // 返回分配的地址
		}
	}
	switchuvm(proc);
	return 0;
}

int
myreduceproc(int address){  // 释放 address 开头的内存块
	int prev = 0;
	int index;
	for(index = proc->vm[0].next; index != 0; index = proc->vm[index].next) {
		if(proc->vm[index].address == address && proc->vm[index].length > 0) {
			mydeallocuvm(proc->pgdir, proc->vm[index].address, proc->vm[index].address + proc->vm[index].length);			
			proc->vm[prev].next = proc->vm[index].next;
			proc->vm[index].next = -1;
			proc->vm[index].length = 0;
			break;
		}
		prev = index;
	}
	switchuvm(proc);
	return 0;
}